import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.TreeMap;
import java.util.stream.Collectors;

/**
 * @FileName Solution1338
 * @Description
 * @Author tong.zhou
 * @date 2024-12-15
 **/
public class Solution1338 {

    public int minSetSize(int[] arr) {
        Map<Integer, Integer> valCountMap = new HashMap<>();
        for (Integer val : arr) {
            valCountMap.put(val, valCountMap.getOrDefault(val, 0) + 1);
        }

        List<Map.Entry<Integer, Integer>> countSortList = 
            valCountMap.entrySet().stream()
                .sorted((a, b) -> b.getValue() - a.getValue()).collect(Collectors.toList());

        int result = 0, countSum = 0;
        for (Map.Entry<Integer, Integer> et : countSortList) {
            countSum += et.getValue();
            result++;
            if(countSum >= arr.length / 2){
                return result;
            }
        }
        return result;
    }
}
